<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2012.05.01
 * MaxTest: 21 --&gt; 1.10 sec
 */

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;cassert&gt;
#include &lt;algorithm&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)

typedef long long ll;

const int maxN = 500;
const int maxE = 20002;

int n, m, e = 2, cur[maxN], head[maxN], to[maxE], f[maxE], c[maxE], next[maxE];
int S, T, h[maxN];
ll ex[maxN];

void addE( int a, int b, int x )
{
  to[e] = b, f[e] = 0, c[e] = x, next[e] = head[a], head[a] = e++;
}

int main()
{
  #define NAME "flow2"
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));
  
  scanf("%d%d", &n, &m);
  forn(i, m)
  {
    int a, b, x;
    scanf("%d%d%d", &a, &b, &x);
    a--, b--;
    addE(a, b, x);
    addE(b, a, 0);
  }

  S = 0, T = n - 1;
  h[S] = n;
  memcpy(cur, head, sizeof(head));
  for (int e = head[S]; e; e = next[e])
    ex[to[e]] += c[e], f[e] = c[e], f[e ^ 1] = -f[e];
  
  for (int run = 1; run;)
  {
    run = 0;
    for (int v = 1; v &lt; n - 1; v++)
      if (ex[v] &gt; 0)
      {
        run = 1;
        for (int e = cur[v]; e && ex[v]; e = cur[v] = next[e])
          if (h[to[e]] + 1 == h[v])
          {
            int x = min((ll)c[e] - f[e], ex[v]);
            f[e] += x, f[e ^ 1] -= x;
            ex[to[e]] += x, ex[v] -= x;
          }
        if (ex[v] &gt; 0)
        {
          int u = -1;
          for (int e = head[v]; e && ex[v]; e = next[e])
            if (f[e] &lt; c[e] && (u == -1 || h[u] &gt; h[to[e]]))
              u = to[e];
          h[v] = h[u] + 1;
          cur[v] = head[v];
        }
      }
  }

  printf("%I64d\n", ex[T]);
  forn(i, m)
    printf("%d\n", f[2 * i + 2]);
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
